package com.zjsru.plan2024.oneday;

import java.util.Arrays;

/**
 * 684. 冗余连接
 *
 * @Author: cookLee
 * @Date: 2024-10-27
 */
public class FindRedundantConnection {

    /**
     * 主
     * \
     * 输入: edges = [[1,2], [1,3], [2,3]]
     * 输出: [2,3]
     * \
     * 输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
     * 输出: [1,4]
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        FindRedundantConnection findRedundantConnection = new FindRedundantConnection();
        int[][] edges = {{1, 2}, {1, 3}, {2, 3}};
        System.out.println(Arrays.toString(findRedundantConnection.findRedundantConnection(edges)));
    }

    /**
     * 查找冗余连接
     *
     * @param edges 边缘
     * @return {@link int[]}
     */
    public int[] findRedundantConnection(int[][] edges) {
        int len = edges.length;
        //记录每个节点的父节点
        int[] parent = new int[len + 1];
        //初始时，每个节点的父节点是其自身。
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
        for (int i = 0; i < len; i++) {
            int[] edge = edges[i];
            int index1 = edge[0];
            int index2 = edge[1];
            //检查两个节点是否已经连通
            if (this.helper(parent, index1) != this.helper(parent, index2)) {
                this.union(parent, index1, index2);
            } else {
                return edge;
            }
        }
        return edges[0];
    }

    /**
     * 合并父节点
     *
     * @param parent 父母
     * @param index1 index1
     * @param index2 index2
     */
    private void union(int[] parent, int index1, int index2) {
        parent[this.helper(parent, index1)] = this.helper(parent, index2);
    }

    /**
     * 帮手：检查对应节点是否已经连通
     *
     * @param parent 父母
     * @param index  索引
     * @return int
     */
    private int helper(int[] parent, int index) {
        if (parent[index] != index) {
            parent[index] = this.helper(parent, parent[index]);
        }
        return parent[index];
    }


}
